package com.qqn.zcy.class03;

import java.util.ArrayList;
import java.util.List;

/**
 * 单向链表和双向链表的反转
 */
public class Code01_ReverseList {

    /**
     * 单链表
     */
    public static class Node {
        /**
         * 存储节点值
         */
        public int value;
        /**
         * 指向下一个节点的索引 如果是最后一个就是  null
         */
        public Node next;

        /**
         * 构造一个新的节点，并初始化其值。
         *
         * @param data 要存储在节点中的值。
         */
        public Node(int data) {
            value = data;
        }
    }

    /**
     * 双链表
     * DoubleNode 静态内部类可以独立于外部类实例化
     */
    public static class DoubleNode {
        /**
         * 存储节点的值
         */
        public int value;
        /**
         * 指向前一个节点的引用，如果是链表的第一个节点，则 last 为 null
         */
        public DoubleNode last;
        /**
         * 指向下一个节点的引用，如果是链表的最后一个节点，则 next 为 null
         */
        public DoubleNode next;

        /**
         * 够造方法用于初始化节点的值，并将 last 和 next 初始化为 null
         *
         * @param data 当前节点的值
         */
        public DoubleNode(int data) {
            value = data;
        }
    }

    /**
     * 单链表的反转
     *
     * @param head 链表头
     * @return 反转后的单链表
     */

    // head
    //   a    ->   b    ->  c  ->  null
    //   c    ->   b    ->  a  ->  null
    public static Node reverseLinkedList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            /**
             * 1、4 步 拿到每一轮操作的单链表
             * 2: 将当前的链表头放入链表尾
             * 3: (1) 记录反转好的链表 (2) 作为下一轮链表头 next 链接的链表
             */
            next = head.next; // next = b-c-null    c-null  null
            head.next = pre;  // *n a-null     *n b-a-null  c-b-a-null
            pre = head;       // *p a-null     *p b-a-null  c-b-a-null   return pre
            head = next;      // *h b-c-null   *h c-null    null
        }
        return pre;
    }

    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            /**
             * 1、5 步 拿到每一轮操作的单链表
             * 2、将当前的链表头放入链表尾
             * 3、将当前的链表头的前一个引用指向的节点 改成 他原本后面引用指向的节点
             * 4、(1) 记录反转好的链表  (2) 作为下一个链表头 next 链接的链表
             */
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 对数器  同样用一个 ArrayList 集合通过存储链表的数据 进而通过 get方法来将集合中的数据重新设置 next引用 达到反转链表的效果
     *
     * @param head 链表头
     * @return 集合的最后一个元素(引用类型的 next 连接了一长串数据)
     */
    public static Node testReverseLinkedList(Node head) {
        if (head == null) {
            return null;
        }
        ArrayList<Node> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        int N = list.size();
        for (int i = 1; i < N; i++) {
            list.get(i).next = list.get(i - 1);
        }
        return list.get(N - 1);
    }

    public static DoubleNode testReverseDoubleList(DoubleNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<DoubleNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        DoubleNode pre = list.get(0);
        int N = list.size();
        for (int i = 0; i < N; i++) {
            DoubleNode cur = list.get(i);
            cur.last = null;
            cur.next = pre;
            pre.last = cur;
            pre = cur;
        }
        return list.get(N - 1);
    }

    /**
     * Node 是自定义的单链表类
     * Node 是单链表的基本构建块，其有两个成员变量 一个是存储当前节点值的 value 一个是指向另外一个节点的引用
     *
     * @param len   需要生成链表的长度 要求 len > 0
     * @param value 每个节点的值的取值范围
     * @return 返回创建的单链表
     */
    public static Node generateRandomLinkedList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        size--;
        /**
         * 创建一个新的 Node 对象，并使用随机生成的整数值初始化其 value 属性
         * 创建单链表的表头
         */
        Node head = new Node((int) (Math.random() * (value + 1)));
        Node pre = head;
        while (size != 0) {
            // 创建一个新的 Node 对象，并使用随机生成的整数值初始化其 value 属性
            Node cur = new Node((int) (Math.random() * (value + 1)));
            pre.next = cur; // 将这个节点链接到上一个节点的 next 引用上   连接
            pre = cur; // 当前关注点向后移动到新链接的节点上     移动关注点
            size--; // 当前链表需要生成的节点减少一个
        }
        return head;
    }

    /**
     * 生成双向链表
     *
     * @param len   需要生成链表的长度 要求 len > 0
     * @param value 每个节点的值的取值范围
     * @return 返回创建的双链表
     */
    public static DoubleNode generateRandomDoubleList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        size--;
        DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
        DoubleNode pre = head;
        while (size != 0) {
            DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
            pre.next = cur;
            cur.last = pre;
            pre = cur;
            size--;
        }
        return head;
    }

    /**
     * 将链表以 ArrayList 集合的形式存储
     *
     * @param head 单链表表头
     * @return 集合形式的单链表
     */
    public static List<Integer> getLinkedOriginOrder(Node head) {
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.value);
            head = head.next;
        }
        return ans;
    }

    /**
     * 检查反转的单链表与原链表是否符合
     *
     * @param origin 原链表的集合形式--此方法中会做反向遍历
     * @param head   反转之后的单链表头
     * @return 反转成功/反转失败
     */
    public static boolean checkLinkedReverse(List<Integer> origin, Node head) {
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 将双向链表以 ArrayList 集合的形式存储
     *
     * @param head 双向链表表头
     * @return 集合形式的双向链表
     */
    public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.value);
            head = head.next;
        }
        return ans;
    }

    /**
     * 检查双向链表反转是否成功
     *
     * @param origin
     * @param head
     * @return
     */
    public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
        DoubleNode end = null;
        /**
         * 主要是检查链表的 next 和 last 都指对了没
         */
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            end = head; // end 最终会跑到双向链表的尾部
            head = head.next;
        }
        for (int i = 0; i < origin.size() - 1; i++) {
            if (!origin.get(i).equals(end.value)) {
                return false;
            }
            end = end.last;
        }
        return true;
    }

    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTime = 100000;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            Node node1 = generateRandomLinkedList(len, value);
            List<Integer> list1 = getLinkedOriginOrder(node1);
            node1 = reverseLinkedList(node1);
            if (!checkLinkedReverse(list1, node1)) {
                System.out.println("Oops!");
            }

            Node node2 = generateRandomLinkedList(len, value);
            List<Integer> list2 = getLinkedOriginOrder(node2);
            node2 = testReverseLinkedList(node2);
            if (!checkLinkedReverse(list2, node2)) {
                System.out.println("Oops2!");
            }
            //
            DoubleNode node3 = generateRandomDoubleList(len, value);
            List<Integer> list3 = getDoubleListOriginOrder(node3);
            node3 = reverseDoubleList(node3);
            if (!checkDoubleListReverse(list3, node3)) {
                System.out.println("Oops3!");
            }
        }
        System.out.println("test finish!");
    }
}
